package com.atguigu.algorithm;

import java.util.Arrays;

public class TheShortestDigest2 {
    public static void main(String[] args) {
        solve2(new String[]{"a","b","c","d","h","e","f","c","c","d","e","f","d","c"},
                new String[]{"c","e","d"});
    }
    public static void solve2(String[] words,String[] keys){
        //begin和end 用于在找到更短的包含全部关键字的子数组时更新
        int begin=-1;
        int end=-1;
        int p2=-1; //上一次囊括了所有关键字的右边界
        int min=Integer.MAX_VALUE;
        int[] keyFound=new int[keys.length];
        for(int i=0;i<words.length;i++){
            Arrays.fill(keyFound,0);
            int index=indexOf(keys,words[i]);
            if(index==-1){
                continue;
            }else{
                keyFound[index]=1; //标记一下
            }
            int j;
            if(p2!=-1){
                j=p2;
            }else{
                j=i+1;
            }
            for(;j<words.length;j++){
                int index1=indexOf(keys,words[j]);
                if(index1==-1 || keyFound[index1]==1){ //如果已经包含该关键字，或者不是关键字就跳过
                    continue;
                }else { //找到了没发现过的关键字
                    keyFound[index1]=1;//标记一下
                    if(sum(keyFound)==keys.length){ //全部到齐
                        p2=j; //将右边界更新为p2
                        if(j-i+1<min){
                            min=j-i+1;
                            begin=i;
                            end=j;
                        }
                        break;
                    }
                }
            }
        }
        print(words,begin,end);
    }
    public static void print(String[] words,int begin,int end){
        for(int i=begin;i<=end;i++){
            if(i==end){
                System.out.print(words[i]);
                return;
            }
            System.out.print(words[i]+" ");
        }
    }
    public static int indexOf(String[] keys,String word){
        for(int i=0;i<keys.length;i++){
            if(keys[i].equals(word)){
                return i;
            }
        }
        return -1;
    }
    public static int sum(int[] arr){
        int sum=0;
        for(int i=0;i<arr.length;i++){
            sum+=arr[i];
        }
        return sum;
    }
}
